package leetcode.dfs.common;

import leetcode.tree.common.TreeNode;

import java.util.Arrays;

public class DFSUtils {

    public static boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        int curSum = 0;
        return solveHasPathSum(root, targetSum, curSum);
    }

    private static boolean solveHasPathSum(TreeNode root, int targetSum, int curSum) {
        if (root == null) {
            return curSum == targetSum;
        }
        curSum = curSum + root.val;
        if (root.left == null && root.right == null) {
            return curSum == targetSum;
        }
        boolean left = false;
        if (root.left != null) {
            left = solveHasPathSum(root.left, targetSum, curSum);
        }
        boolean right = false;
        if (root.right != null) {
            right = solveHasPathSum(root.right, targetSum, curSum);
        }
        return left || right;
    }

    public static int sumNumbers(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return root.val;
        }
        int result;
        int resultOfLastLevel = 0;
        result = solveSumNumbers(root, resultOfLastLevel);
        return result;
    }

    private static int solveSumNumbers(TreeNode root, int resultOfLastLevel) {
        if (root == null) {
            return resultOfLastLevel;
        }
        if (root.left == null && root.right == null) {
            return resultOfLastLevel * 10 + root.val;
        }
        int sum = 0;
        if (root.left != null) {
            sum += solveSumNumbers(root.left, resultOfLastLevel * 10 + root.val);
        }
        if (root.right != null) {
            sum += solveSumNumbers(root.right, resultOfLastLevel * 10 + root.val);
        }
        return sum;
    }

    public static int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        if (grid.length == 1) {
            return Arrays.stream(grid[0]).sum();
        }
        int m = grid.length;
        int n = grid[0].length;
        return solveMinPathSum(grid, 0, 0, Integer.MAX_VALUE, 0, m, n);
    }

    private static int solveMinPathSum(int[][] grid, int row, int col, int result, int curSum, int m, int n) {
        if (curSum >= result) {
            return result;
        }
        if (row > m - 1 || col > n - 1) {
            return result;
        }
        curSum += grid[row][col];
        if (row == m - 1 && col == n - 1) {
            return Math.min(result, curSum);
        }
        if (row < m - 1 && col == n - 1) {
            result = solveMinPathSum(grid, row + 1, col, result, curSum, m, n);
        } else if (row == m - 1 && col < n - 1) {
            result = solveMinPathSum(grid, row, col + 1, result, curSum, m, n);
        } else if (row < m - 1 && col < n - 1) {
            result = Math.min(solveMinPathSum(grid, row + 1, col, result, curSum, m, n), solveMinPathSum(grid, row, col + 1, result, curSum, m, n));
        }
        return result;
    }

    public static TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null) {
            return t2;
        }
        if (t2 == null) {
            return t1;
        }
        TreeNode merged = new TreeNode(t1.val + t2.val);
        merged.left = mergeTrees(t1.left, t2.left);
        merged.right = mergeTrees(t1.right, t2.right);
        return merged;
    }

    public static int sumRootToLeaf(TreeNode root) {
        if (root.left == null && root.right == null) {
            return root.val;
        }
        int[] result = new int[1];
        int curSum = 0;
        solveSumRootToLeaf(root, result, curSum);
        return result[0];
    }

    private static void solveSumRootToLeaf(TreeNode root, int[] result, int curSum) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            curSum = (curSum << 1) + root.val;
            result[0] += curSum;
            return;
        }
        curSum = (curSum << 1) + root.val;
        solveSumRootToLeaf(root.left, result, curSum);
        solveSumRootToLeaf(root.right, result, curSum);
    }
}
